9635. Транспортная
система
Транспортная система города
Баку состоит из n перекрестков и m двухсторонних дорог, соединяющих эти перекрестки. Каждая дорога
соединяет ровно два перекрестка, и никакая пара перекрестков не может быть
соединена больше, чем одной дорогой. Перемещаясь по этим дорогам, можно поехать
с любого перекрестка на любой другой. Расстоянием между двумя перекрестками
считается минимальное количество дорог среди всех путей, соединяющих эти
перекрестки.
Чтобы улучшить транспортную
систему, мер города потребовал у директора транспортной системы провести новую
дорогу. Однако, мер купил новую машину и каждый день наслаждается поездкой из
дома на работу и с работы домой. Ему не хочется, чтобы уменьшилось расстояние
между перекрестком s, где находится его дом и
перекрестком t, где находится его работа.
Помогите директору транспортной системы решить эту задачу, так как он
обязательно должен выполнить требование мера.
Ваша задача найти количество
таких пар несоединенных перекрестков, что проведя дорогу между ними, расстояние
между перекрестками s и t не уменьшится.
Вход.
В первой строке даны четыре целых числа: количество перекрестков n (1 ≤ n ≤ 103), количество
дорог m (1 ≤ m ≤ 105),
перекресток s, где находится дом, перекресток t,
где находится работа (1 ≤ s, t ≤ n, s ≠ t). В последующих m строках, i-я строка содержит два числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi). Они означают, что между
перекрестками ui и vi имеется двухсторонняя дорога.
Выход. Выведите искомое в условии
задачи количество пар перекрестков.
|
Пример входа 1 |
Пример выхода 1 |
|
5 4 1 5 1 2 2 3 3 4 4 5 |
0 |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
5 4 3 5 1 2 2 3 3 4 4 5 |
5 |
РЕШЕНИЕ
графы,
поиск в ширину
Анализ алгоритма
Запустим поиск в
ширину из стартовой s и финальной f
вершины. Соответственно
кратчайшие расстояния от s занесем в
массив distS,
кратчайшие расстояния от f занесем в
массив distF.
Пусть optDistance –
кратчайшее расстояние между s и f в исходном графе.
Рассмотрим,
можно ли провести новую дорогу между вершинами i и j.
При проведении
дороги между i и j образуются новые пути s → i → j → f длины distS[i] + 1 + distF[j] и s → j → i → f длины distS[j] + 1 + distF[i]. Если
хотя бы одно из этих расстояний будет меньше optDistance, то
проведение дороги (i, j) уменьшит
кратчайшее расстояние между s и f и в
таком случае она нам не подходит.
Остается
перебрать все возможные пары i и j и проверить, не уменьшит ли новая дорога (i, j) кратчайшее
расстояние между s и f.
Пример
Граф из
первого теста приведен слева. Кратчайшее расстояние от 1 до 5 равно 4. Какую бы
новую дорогу мы бы не проводили, расстояние между 1 и 5 сократится. Поэтому ни
одной требуемой дороги не существует.
Граф из
второго теста приведен справа. Кратчайшее расстояние от 3 до 5 равно 2. Жирными
линиями показаны возможные дороги. Какая бы одна из этих дорог не была бы
построена, расстояние между 3 и 5 не уменьшится.
Реализация алгоритма
Объявим константу MAX – максимально возможное
количество вершин графа.
#define MAX 1001
Объявим матрицу смежности g.
int g[MAX][MAX], distS[MAX], distF[MAX];
Функция bfs реализует поиск в
ширину из вершины start. Ей передается массив кратчайших расстояний dist.
void bfs(int start, int *dist)
{
Инициализируем массив кратчайших расстояний dist.
for (int i = 0; i <=
n; i++) dist[i] = -1;
dist[start] = 0;
Объявим очередь. Занесем в нее стартовую вершину.
queue<int> q;
q.push(start);
Пока очередь не пуста, извлекаем из нее вершину v.
while (!q.empty())
{
int v = q.front(); q.pop();
Перебираем вершины to, смежные с v. Если вершина to еще не
посещена, то вычисляем кратчайшее расстояние dist[to]
до нее и кладем ее в очередь.
for (int to = 1; to <= n; to++)
if (g[v][to] && dist[to] == -1)
{
q.push(to);
dist[to] = dist[v] + 1;
}
}
}
Основная часть программы. Читаем входные данные.
scanf("%d %d %d %d", &n, &m, &s, &f);
memset(g, 0, sizeof(g));
Читаем неориентированный граф.
for (i = 0; i < m; i++)
{
scanf("%d
%d", &a, &b);
g[a][b] = g[b][a] = 1;
}
Запускаем поиск в ширину из вершин s и f. Кратчайшие расстояния соответственно занесем в массивы distS
и distF.
bfs(s, distS);
bfs(f, distF);
Кратчайшее расстояние между s и f
в исходном графе равно optDistance.
optDistance = distS[f];
Перебирвем пары вершин i и j и стараемся провести между ними новую дорогу. В переменной res подсчитываем
количество возможных новых дорог.
res = 0;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)
Если между i и j дороги еще нет, то вычисляем длины кратчайших путей s → i → j → f и s → j → i → f. Если
они не меньше optDistance, то такую
дорогу строить можно.
if (g[i][j] == 0)
{
if ((distS[i] +
distF[j] + 1 >= optDistance) &&
(distS[j] +
distF[i] + 1 >= optDistance))
res++;
}
Выводим ответ.
printf("%d\n", res);
Java реализация
import java.util.*;
public class Main
{
static int g[][], distS[], distF[];
static int n, m, s, f;
static void bfs(int start, int dist[])
{
Arrays.fill(dist,-1);
dist[start] = 0;
Queue<Integer> q = new
LinkedList<Integer>();
q.add(start);
while(!q.isEmpty())
{
int v = q.poll();
for (int to = 1; to <= n; to++)
if (g[v][to] == 1
&& dist[to] == -1)
{
q.add(to);
dist[to] = dist[v] + 1;
}
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
n = con.nextInt();
m = con.nextInt();
s = con.nextInt();
f = con.nextInt();
g = new int[n+1][n+1];
distS = new int[n+1];
distF = new int[n+1];
for (int i = 1; i <= m; i++)
{
int a = con.nextInt();
int b = con.nextInt();
g[a][b] = g[b][a] = 1;
}
bfs(s, distS);
bfs(f, distF);
int optDistance = distS[f];
int res = 0;
for(int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (g[i][j] == 0)
{
if ((distS[i] + distF[j] + 1 >= optDistance) &&
(distS[j] + distF[i] + 1 >= optDistance))
res++;
}
System.out.println(res);
con.close();
}
}